package day5;

/**
 * 
 * 快速排序3.0版本，随机选择分区
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] test=new int[]{5,2,3,7,3,6};
        quickSort(test);
        for (int i = 0; i < test.length; i++) {
            System.out.println(test[i]);
        }
    }
    
    public static void quickSort(int[] array){
        if (array==null||array.length<2) {
            return;
        }
        quickSort(array,0,array.length-1);
    }

    private static void quickSort(int[] array, int left, int right) {
        if (left<right) {
            //随机选择一个数交换到数组末尾作为排序的标准，即荷兰国旗问题中的flag
            swap(array,left+(int)Math.random()*(right-left+1),right);
            //分区找到大于区和小于区的边界
            int[] border=partition(array,left,right);
            //处理数组中<的区域
            quickSort(array,left,border[0]-1);
            //处理数组中>的区域
            quickSort(array,border[1]+1,right);
        }
    }

    /**
     * 
     * 这是一个处理arr[l..r]的函数
     * 默认以arr[r]做划分，arr[r]->p   <p   ==p  >p
     * 返回等于区域(==p区)的左右边界，所以返回一个长度为2的数组
     * @param array 数组
     * @param left 数组最左侧索引
     * @param right 数组最右侧索引
     * @return 分类好中间区域的最左侧和最右侧
     */
    private static int[] partition(int[] array, int left, int right) {
        int less=left-1;//<区右边界
        int more=right;//>区左边界
        while (left<more) {//left代表当前数的位置，arr[right] -> 划分值
            //荷兰国旗问题
            if (array[left]<array[right]) {
                swap(array, ++less, left++);
            }else if (array[left]>array[right]) {
                swap(array, --more, left);
            }else{
                left++;
            }
        }
        swap(array, more, right);
        return new int[]{less+1,more};
    }

    private static void swap(int[] array, int i, int j) {
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    
}
